Problem 447 Number of Boomerangs
该问题给了我们一个二维数组,数组中每个元素是一个点,其拥有x和y的坐标.要求找出所有满足条件的三元组,而条件是三元组中第一个元素到第二个元素和第一个元素到第三个元素的距离相同.
主要思路:
以第一个点为中心点进行遍历,利用hashMap存储距离到达中心点相同的点的个数,最后由于两个点之间的位置可以互换,所以需要对计数器*2
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public int numberOfBoomerangs(int[][] points) {
if(points.length<3){
return 0;
}
int count = 0;
Map<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0;i < points.length;i++){
hashMap.clear();
for (int j = 0;j < points.length;j++){
if (i == j){
continue;
}
int distance = (points[j][0]-points[i][0])*(points[j][0]-points[i][0]) + (points[j][1]-points[i][1]) * (points[j][1]-points[i][1]);
count += hashMap.getOrDefault(distance,0) * 2;
hashMap.put(distance,hashMap.getOrDefault(distance,0) + 1);
}
}
return count;
}
}
代码说明:
这里的count之所以每次执行hashMap.getOrDefault(distance,0)*2的操作是为了模拟组合操作,新的距离产生的时候其map中对应的值为0,因为此时只有1个元素,所以count=0*2,之后该距离填入map,当有第二个相同距离的元素进来时,count+=1*2=2,map中该距离的值变为2,继续以上操作,你会发现count的变化规律是0+2+4+6+8+10+…,刚好对应的是Cn取2的模式(除第一次外),也就是对应有多少种情况.
Problem 453 Minimum Moves to Equal Array Elements
该问题要求判断数组里的每个元素是否相同,而每次的变化规律是除某一元素外,其余所有元素都加1,求出满足所有元素相同要求的最小的移动步数.
主要思路:
该问题最正常的思路就是每次找出最大值,然后将其他所有值加上1,判断是否满足条件并重复上述过程.这样自然是在逻辑上没问题,但会出现超时问题.所以需要一点技巧,换个角度思考,其它所有值+1相当于未选中的值-1,这样只需要累加各个值和最小值的差异即可.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE, count = 0;
for(int n : nums) {
min = Math.min(min, n);
}
for(int n : nums) {
count += n - min;
}
return count;
}
}
Problem 459 Repeated Substring Pattern
判断一个字符串能不能通过它的子串的重复累加得到
主要思路:
如果通过获取所有子串判断的话会出现超时问题,所以需要通过巧妙的判断解决,那就是将字符串叠加一次成两倍,然后掐头去尾,如果原字符串在修改中的字符串中则返回true.
简单举例来说,如果字符串只有1位,其子串必为空,自然返回false.如有2位,两倍后掐头去尾,如果原字符串满足条件,那么两倍化之后的字符串中自然包含原来的字符串,比如abab,两倍化之后为abababab,去掉首尾的a和b变为bababa,其原串abab包含其中,返回true.
代码实现:1
2
3
4
5
6class Solution {
public boolean repeatedSubstringPattern(String s) {
String ss = s + s;
return ss.substring(1, ss.length()-1).contains(s);
}
}
Problem 475 Heaters
该题简单来说就是有一堆房子,其中有一些是取暖房,要求求出取暖房辐射的半径,这个半径要保证所有的房子不被冻死.
主要思路:
这个题目需要用到排序和查找,排序是为了找出房子和取暖房的顺序,方便遍历.而查找是用于查找房子位于哪两个取暖房的中间,或者位于取暖房的左边(房子编号为第一个时),或者位于取暖房的右边(房子编号为最后一个时),如果在房子在两个取暖房中间的话,只需要求出房子到两边的最小值即可,当求完所有半径值之后取其中最大值作为半径.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int radius = 0;
int i = 0;
for (int house:houses){
while(i<heaters.length-1&&house>heaters[i])
i++;
if (i!=0)
radius = Math.max(radius,Math.min(Math.abs(house-heaters[i-1]),Math.abs(house-heaters[i])));
else
radius = Math.max(Math.abs(house-heaters[0]),radius);
}
return radius;
}
}
代码说明:
主要是while循环,其中包含两个条件,第一个条件时为了保证i不越界,第二个条件是为了保证取暖房的值会大于当前房子的值(除非取暖房已经遍历到了最后一个,即剩下所有房子编号都比取暖房最后一个编号要大).